package com.fw.leetcode.matrix;

import com.fw.leetcode.LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 54. Spiral Matrix
 *
 * Given an (m x n) matrix, return all elements of the matrix in spiral order.
 *
 * Example 1:
 *  Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
 *  Output: [1,2,3,6,9,8,7,4,5]
 *
 * Example 2:
 *  Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 *  Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 *
 * Constraints:
 *  m == matrix.length
 *  n == matrix[i].length
 *  1 <= m, n <= 10
 *  -100 <= matrix[i][j] <= 100
 */
public class Num_0054 implements LeetCode {

    private interface Solution {
        List<Integer> spiralOrder(int[][] matrix);

        default void assertExpected(int[][] matrix, int[] expected) {
            int[] result = spiralOrder(matrix).stream().mapToInt(Integer::intValue).toArray();
            if (!Arrays.equals(result, expected)) {
                spiralOrder(matrix);
            }
        }
    }

    private static class VectorLayerSolution implements Solution {

        static final int[][] DIRECTIONS = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 顺时针4个方向

        private boolean unavailable(int[][] matrix, int layer, int cntInLayer, int i, int j) {
            return i < layer || j < layer
                    || i > matrix.length - 1 - layer
                    || j > matrix[0].length - 1 - layer
                    || (i == layer && j == layer && cntInLayer > 0); // 再次访问起点判断为终止
        }

        @Override
        public List<Integer> spiralOrder(int[][] matrix) { // 矩阵螺旋 最优：方向向量-分层法（避免标记），时O(mn) 空O(1)
            /*
             * Matrix 1:
             *  [1,2,3]
             *  [4,5,6]
             *  [7,8,9]
             * i = 0 0 0 1 2 2 2 1   1
             * j = 0 1 2 2 2 1 0 0   1
             *
             * Matrix 2:
             *  [1, 2, 3, 4]
             *  [5, 6, 7, 8]
             *  [9,10,11,12]
             * i = 0 0 0 0 1 2 2 2 2 1    1 1
             * j = 0 1 2 3 3 3 2 1 0 0    1 2
             *
             * Matrix 3:
             *  [ 1, 2, 3, 4]
             *  [ 5, 6, 7, 8]
             *  [ 9,10,11,12]
             *  [13,14,15,16]
             * i = 0 0 0 0 1 2 3 3 3 3 2 1    1 1 2 2
             * j = 0 1 2 3 3 3 3 2 1 0 0 0    1 2 2 1
             *
             * coordinate:   [ 0, 1] j->
             *    --- j      [ 1, 0] i->
             *   |           [ 0,-1] j<-
             *   i           [-1, 0] i<-
             */
            List<Integer> path = new ArrayList<>(matrix.length * matrix[0].length);
            int i = 0, j = 0, idx = 0, layer = 0, cntInLayer = 0;
            int[] curDirection = DIRECTIONS[idx];

            while (true) {
                // 若访问过（或边界外），改变方向
                if (unavailable(matrix, layer, cntInLayer, i, j)) {
                    // 先回退步子
                    i -= curDirection[0];
                    j -= curDirection[1];
                    // 改变方向后再前进步子
                    curDirection = DIRECTIONS[(++idx) & 0x3];
                    if ((idx >> 2) > layer) {
                        // 若发生层数递进，层内计数归零，此时起点坐标即：坐标归位层头第一位置（左上角）
                        layer = idx >> 2;
                        cntInLayer = 0;
                    }
                    i += curDirection[0];
                    j += curDirection[1];
                    // 若顺时针改变方向一次后依然无法访问，则结束
                    if (unavailable(matrix, layer, cntInLayer, i, j)) {
                        break;
                    }
                }
                path.add(matrix[i][j]); // 访问
                cntInLayer++; // 层内计数+1
                i += curDirection[0]; // 继续前进
                j += curDirection[1];
            }

            return path;
        }
    }

    private static class VectorMarkSolution implements Solution {

        static final int[][] DIRECTIONS = new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; // 顺时针4个方向
        static final int VISITED = -999; // 标记访问过位置

        private boolean unavailable(int[][] matrix, int i, int j) {
            return i < 0 || j < 0 || i > matrix.length - 1 || j > matrix[0].length - 1 || matrix[i][j] == VISITED;
        }

        @Override
        public List<Integer> spiralOrder(int[][] matrix) { // 方向向量-访问原位标记法，时O(mn) 空O(1)
            /*
             * Matrix 1:
             *  [1,2,3]
             *  [4,5,6]
             *  [7,8,9]
             * i = 0 0 0 1 2 2 2 1 1
             * j = 0 1 2 2 2 1 0 0 1
             *
             * Matrix 2:
             *  [1, 2, 3, 4]
             *  [5, 6, 7, 8]
             *  [9,10,11,12]
             * i = 0 0 0 0 1 2 2 2 2 1 1 1
             * j = 0 1 2 3 3 3 2 1 0 0 1 2
             *
             * Matrix 3:
             *  [ 1, 2, 3, 4]
             *  [ 5, 6, 7, 8]
             *  [ 9,10,11,12]
             *  [13,14,15,16]
             * i = 0 0 0 0 1 2 3 3 3 3 2 1 1 1 2 2
             * j = 0 1 2 3 3 3 3 2 1 0 0 0 1 2 2 1
             *
             * coordinate:   [ 0, 1] j->
             *    --- j      [ 1, 0] i->
             *   |           [ 0,-1] j<-
             *   i           [-1, 0] i<-
             */
            List<Integer> path = new ArrayList<>(matrix.length * matrix[0].length);
            int i = 0, j = 0, idx = 0;
            int[] curDirection = DIRECTIONS[idx];

            while (true) {
                // 若访问过（或边界外），改变方向
                if (unavailable(matrix, i, j)) {
                    // 先回退步子
                    i -= curDirection[0];
                    j -= curDirection[1];
                    // 改变方向后再前进步子
                    curDirection = DIRECTIONS[(++idx) & 0x3];
                    i += curDirection[0];
                    j += curDirection[1];
                    // 若顺时针改变方向一次后依然无法访问，则结束
                    if (unavailable(matrix, i, j)) {
                        break;
                    }
                }
                path.add(matrix[i][j]); // 访问
                matrix[i][j] = VISITED; // 标记访问过
                i += curDirection[0]; // 继续前进
                j += curDirection[1];
            }

            return path;
        }

    }

    public static void main(String[] args) {
        Solution solution = new VectorLayerSolution();
        solution.assertExpected(new int[][]{{1,2,3},{4,5,6},{7,8,9}}, new int[]{1,2,3,6,9,8,7,4,5});
        solution.assertExpected(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}}, new int[]{1,2,3,4,8,12,11,10,9,5,6,7});
    }
}
